/*
 * Copyright (c) 2009-2013 EvTech Project
 * All rights reserved.
 * 
 * This file is part of Game packet.
 *
 * Game packet is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or 
 * (at your option) any later version.
 *
 * Game packet is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with Game packet.  If not, see <http://www.gnu.org/licenses/>.
 * 
 */
package fi.honkalampisaatio.utilities.math;

public final class FFT {
	// luokka, joka toteuttaa nimensä mukaisesti FFT:n
	private int n, nu;

	private int bitrev(int j) {
		int j2;
		int j1 = j;
		int k = 0;
		for (int i = 1; i <= nu; i++) {
			j2 = j1 / 2;
			k = 2 * k + j1 - 2 * j2;
			j1 = j2;
		}
		return k;
	}

	public final float[] fftMag(float[] x) {
		// oletetaan, että n on kahden potenssi
		n = x.length;
		nu = (int) (Math.log(n) / Math.log(2));
		int n2 = n / 2;
		int nu1 = nu - 1;
		float[] xre = new float[n];
		float[] xim = new float[n];
		float[] mag = new float[n2];
		float tr, ti, p, arg, c, s;
		for (int i = 0; i < n; i++) {
			xre[i] = x[i];
			xim[i] = 0.0f;
		}
		int k = 0;
		for (int l = 1; l <= nu; l++) {
			while (k < n) {
				for (int i = 1; i <= n2; i++) {
					p = bitrev(k >> nu1);
					arg = 2 * (float) Math.PI * p / n;
					c = (float) Math.cos(arg);
					s = (float) Math.sin(arg);
					tr = xre[k + n2] * c + xim[k + n2] * s;
					ti = xim[k + n2] * c - xre[k + n2] * s;

					xre[k + n2] = xre[k] - tr;
					xim[k + n2] = xim[k] - ti;
					xre[k] += tr;
					xim[k] += ti;
					k++;
				}
				k += n2;
			}
			k = 0;
			nu1--;
			n2 = n2 / 2;
		}
		k = 0;
		int r;
		while (k < n) {
			r = bitrev(k);
			if (r > k) {
				tr = xre[k];
				ti = xim[k];
				xre[k] = xre[r];
				xim[k] = xim[r];
				xre[r] = tr;
				xim[r] = ti;
			}
			k++;
		}
		mag[0] = (float) (Math.sqrt(xre[0] * xre[0] + xim[0] * xim[0])) / n;
		for (int i = 1; i < n / 2; i++)
			mag[i] = 2 * (float) (Math.sqrt(xre[i] * xre[i] + xim[i] * xim[i]))
					/ n;
		mag[0] = 0;
		return mag;
	}
}
